package edu.rit.checkers;

import java.util.Comparator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

import edu.rit.pj.BarrierAction;
import edu.rit.pj.Comm;
import edu.rit.pj.ParallelRegion;
import edu.rit.pj.ParallelTeam;

/**
 * @author Ian Tewskbury (ict8574@rit.edu)
 */
public class CheckersSmp {
	/**
	 * used as a parameter for buildTree if thread count is specified
	 * by command line
	 */
	public static final int UNSPECIFIED_THREAD_COUNT = -1;
	
	/**
	 * The usage message for running this program
	 */
	private static final String USAGE =
		"usage: CheckersSeq -Dpj.nt=<NT> " +
		"<startDepth> <increaseDepth> <maxTime> <maxTimePerDepth>\n" +
		"<NT> is the number of parallel threads\n" +
		"<startDepth> the start depth of the tree\n" +
		"<increaseDepth> the amount to increase the depth " +
			"of the tree by if time allows\n" +
		"<maxTime> the max time to run the search\n" +
		"<maxTimePerDepth> the max time to spend searching " +
			"each depth increase\n";

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		//PJ init
		Comm.init(args);
		
		int[] parsedArgs = CheckersSmp.parseArgs(args);
		
		if(parsedArgs != null) {
			CheckersSmp.runSmpTest(parsedArgs[0], parsedArgs[1], parsedArgs[2],
				parsedArgs[3], true, CheckersSmp.UNSPECIFIED_THREAD_COUNT);
		}
	}
	
	/**
	 * 
	 * @param args
	 * @return
	 */
	private static int[] parseArgs(String[] args){
		int[] parsedArgs = null;
		
		if(args.length == 4) {
			parsedArgs = new int[4];
			try {
				parsedArgs[0] = Integer.parseInt(args[0]);
				parsedArgs[1] = Integer.parseInt(args[1]);
				parsedArgs[2] = Integer.parseInt(args[2]);
				parsedArgs[3] = Integer.parseInt(args[3]);
			} catch(NumberFormatException e) {
				parsedArgs = null;
				System.out.println(USAGE);
			}
		} else {
			System.out.println(USAGE);
		}
		
		return parsedArgs;
	}
	
	/**
	 * 
	 * @param args
	 * @return
	 * @throws Exception
	 */
	public static long runSmpTest(int startDepth, int depthIncrease,
			int timeLimit, int timeLimitForDepth,
			boolean printInfo, int numThreads) throws Exception {
		
		long tStart, tABStart;
		
		//get start time
		tStart = System.currentTimeMillis();
		
		//create logger
		Logger log = new Logger(System.out);
		log.loggerOn(printInfo);
		
		//build the tree
		log.println("SEARCH TREE");
		ConfigTree tree = null;
		tree = CheckersSmp.buildTree(startDepth, depthIncrease, timeLimit,
			timeLimitForDepth, numThreads);
		
		//print tree info and search time
		log.println(tree);
		log.println("Search Time: " +
			(System.currentTimeMillis() - tStart));
		
		//do a final alpha beta and print its running time
		log.println("\nFINAL ALPHA-BETA");
		tABStart = System.currentTimeMillis();
		tree.alphaBeta();
		log.println(tree);
		log.println("Final Alpha-Beta Time: " +
			(System.currentTimeMillis() - tABStart));
		
		//return total running time
		log.println("Total Time: " +
			(System.currentTimeMillis() - tStart));
		
		return tree.size();
	}
	
	/**
	 * 
	 * @param timeLimit
	 * @param timeLimitForDepth
	 * @return
	 * @throws Exception 
	 */
	private static ConfigTree buildTree(final int startDepth, final int depthIncrease,
		final int timeLimit, final int timeLimitForDepth, int numThreads)
		throws Exception {
		
		ConfigNode root = new ConfigNode();
		final ConfigTree rootTree = new ConfigTree(startDepth, root, false);
		
		//if thread count specified use that amount, otherwise leave it
		//	unspecified and it will be based on command line arguments
		ParallelTeam team = null;
		if(numThreads != UNSPECIFIED_THREAD_COUNT) {
			team = new ParallelTeam(numThreads);
		} else {
			team = new ParallelTeam();
		}
		
		team.execute(new ParallelRegion() {
			@Override
			public void run() throws Exception {
				
				//when exploring nodes need to start with the lowest
				//	farthest left for depth first search
				SortedSet<ConfigNode> localUnexploredNodes =
					new TreeSet<ConfigNode>(new Comparator<ConfigNode>() {
						/**
						 * 
						 * @param o1
						 * @param o2
						 * @return
						 */
						public int compare(ConfigNode o1, ConfigNode o2) {
							//explore deeper nodes first
							int retVal = o2.depth - o1.depth;
							if(retVal == 0) {
								//explore furtherest left nodes first
								retVal = o1.nodeNum - o2.nodeNum;
							}
							
							return retVal;
						}
					});
				
				//while there is still time keep exploring
				List<ConfigNode> children;
				ConfigNode unexploredNode;
				final long tStartTotal = System.currentTimeMillis();
				while((System.currentTimeMillis() - tStartTotal) < timeLimit) {
					
					boolean atMaxDepth = false;
					long tStartDepth = System.currentTimeMillis();
					while( rootTree.hasUnassignedNodes() &&
						(System.currentTimeMillis() - tStartDepth) <
							timeLimitForDepth
						&& (System.currentTimeMillis() - tStartTotal) <
							timeLimit) {
						
						//get the next unassigned node
						ConfigNode assignedNode =
							rootTree.getNextUnassignedNode();
						
						if(assignedNode != null) {
							//create local tree
							final ConfigTree localTree =
								new ConfigTree(rootTree.maxDepth, assignedNode, true);
							
							//generate its children
							assignedNode.generateChildren();
							
							//TODO EXPLAIN
							if(assignedNode.children.size() > 1) {
								rootTree.addNode(
									assignedNode.children.get(0), false);
								
								children = assignedNode.children.subList(
									1, assignedNode.children.size());
								atMaxDepth = !localTree.addNodes(children, true);
							} else {
								children = assignedNode.children;
								atMaxDepth = !localTree.addNodes(children, true);
							}
							
							if(!atMaxDepth) {						
								//because we told the tree the children are
								//	assigned we need to explore them up to max
								//	depth or max time
								localUnexploredNodes.addAll(children);
								
								//explore local nodes
								while(!localUnexploredNodes.isEmpty() &&
									(System.currentTimeMillis() - tStartDepth) <
										timeLimitForDepth) {
									
									//get the next unexplored node
									unexploredNode =
										localUnexploredNodes.first();
									localUnexploredNodes.remove(unexploredNode);
									
									unexploredNode.generateChildren();
									children = unexploredNode.children;
									atMaxDepth =
										!localTree.addNodes(children, true);
									if(!atMaxDepth) {
										localUnexploredNodes.addAll(children);
									}
								}
								
								if(!localUnexploredNodes.isEmpty()) {
									localTree.addNodes(localUnexploredNodes, false);
								}
								
							}//END if not at max depth
							
							if(localTree.addedNodes() > 0) {
								//merge local tree with root tree
								rootTree.mergeTree(localTree);
							}
	
						}//END if assigned node not null
					}//END while and max time, and depth time
					
					//this should only be done by one thread
					this.barrier(new BarrierAction() {
						@Override
						public void run() throws Exception {
							//only do this if we have more time, otherwise we
							//	have run out of time and will return the
							//	current tree
							if((System.currentTimeMillis() - tStartTotal) <
								timeLimit) {
								
								//TODO REMOVE ME
								System.out.println(this.getThreadIndex() + " BEFORE alpha beta and increase depth. added = " + rootTree.addedNodes());
								
								rootTree.alphaBeta();
								rootTree.increaseMaxDepth(depthIncrease);
								
								//TODO REMOVE ME
								System.out.println(this.getThreadIndex() + "  AFTER alpha beta and increase depth.");
								
							}
						}
					});
				}//END while has max time 
			}//END run
		});//END parallel region
		
		return rootTree;
	}

}
